#ifndef __LINLIST
#define __LINLIST

#include <stdio.h>

/*
void error(char *t, bool ex)
{
	cerr << t << endl;
   if (ex) exit(0);
}
*/


////////////////////////////////////////////////////////////////////////
// LinList  (SLink)
////////////////////////////////////////////////////////////////////////

template <class DATA>
struct SLink
{
   DATA *d;                    	// pointer to the element
   //bool			doDelete;			// flag to delete DATA in destructor   
   SLink<DATA> *next;          	// pointer on the next element of the list
   SLink<DATA> *prev;          	// pointer on previous element of the list

   SLink();
   ~SLink();
};

template <class DATA>
SLink<DATA>::SLink()
{
	d = NULL;
	next = prev = NULL;
   
}

template <class DATA>
SLink<DATA>::~SLink()
{
	delete d;
}

////////////////////////////////////////////////////////////////////////
// LinList
////////////////////////////////////////////////////////////////////////

template <class DATA>
class LinList
{
protected:
    SLink<DATA> *first;         // first element
    SLink<DATA> *last;          // last element
    int anz;                    // size of the list
    SLink<DATA> *akt;           // pointer on the current element
    int akt_index;              // Index of the curent elemnt
//    bool doDelete;				  // flag to delete DATA in destructor    
public:
    LinList();
    virtual ~LinList();
    virtual int get_num() 	     // return size of the list
        { return anz; }         

    virtual void check();       // check if the list is correct (size match the number of elem)

    virtual void insert(DATA *f);	// insert data to the tail
	virtual void insertHead(DATA *f);	// insert data to the head
	 //virtual void noDelete();	  // DATA wird beim loeschen nicht beruecksichtigt
    virtual bool erase();       // delete the current element from the list

    virtual DATA * get(int i);  // return the i-th Element
    virtual DATA * get_first(); // return the first element
    virtual DATA * get_last();  // return the last element
    virtual DATA * get_next();  // return the next element of the current element
    virtual DATA * get_prev();  // return the previous element of the current element

    virtual void	insert_list(LinList *l);	// insert the list l, delete l

	virtual bool isPresent(DATA* d);
	//make resize(int)
	 virtual void resize(int i, DATA defaultValue); 
	 //make set(int)
	 virtual bool set(int i, DATA *d); 
};


template <class DATA>
bool LinList<DATA>::isPresent(DATA* d){
	return false;
}


/*
bool LinList<unsigned int>::isPresent(unsigned int * d){

	unsigned int* currentData = get_first();
								
	do{														
		
		if((*currentData) == (*d)){
			return true;
		}
			
		currentData = get_next();
								
	}while(currentData != get_last());

	return false;
}

*/

template <class DATA>
void LinList<DATA>::insert_list(LinList *l)
{
	cout << "insert list : SHOULD NOT BE THERE" << endl;

   if (l == NULL) return;
   if (l->anz==0) return;

   // stick lists together
   if (l->last != NULL)
	   l->last->next=first;
	if (first != NULL)
	   first->prev=l->last;

    // first, last and size update
    anz+=l->anz;
    first=l->first;

    if (last == NULL)
	 last = l->last;

    // set position to undefined
    akt = NULL;
    akt_index = -1;

    // delete l
    l->first=l->last=NULL;
    l->anz=0; 
	//if we do this, we lose the datas..maybe check later
	delete l;
}

template <class DATA>
LinList<DATA>::LinList()
{
    anz = 0;
    akt_index = -1;
    akt = first = last = NULL;
    
}

template <class DATA>
LinList<DATA>::~LinList()
{
	//cout << "in destructor" << endl;
	SLink<DATA> *hf;

   // Elemente freigeben
   akt = first;
   while (akt != NULL)
   {
	  // cout << "in while destructor : " << akt << endl;
		hf = akt->next;
		delete akt;
		akt = hf;
   }
}

template <class DATA>
void LinList<DATA>::insert(DATA *f)
{
    SLink<DATA> *sd;

    // new link
    sd = new SLink<DATA>();
    sd->d = f;

    // put in the list
    sd->next = NULL;
    sd->prev = last;
    if (last != NULL)
	last->next = sd;

    // first, last ans size update
    anz++;
    last = sd;
    if (first == NULL)
	first = sd;

    // Position ist undefiniert
  //  akt = NULL;
  //  akt_index = -1; // no need anymore because insert at the end of the list
}


template <class DATA>
void LinList<DATA>::insertHead(DATA *f)
{
    SLink<DATA> *sd;

    // new link
    sd = new SLink<DATA>();
    sd->d = f;

    // put in the list
    sd->next = first;
    sd->prev = NULL;
    if (first != NULL)
	first->prev = sd;

    // first, last ans size update
    anz++;
    first = sd;
    if (last == NULL)
	last = sd;

    // Position ist undefiniert
    akt = NULL;
    akt_index = -1;
}



/*
template <class DATA>
void LinList<DATA>::noDelete()	  										// DATA wird beim loeschen nicht beruecksichtigt
{
	if (akt->doDelete) akt->doDelete=false;
 		else error("LinList::noDelete: not owner of DATA", true);
}
*/
template <class DATA>
bool LinList<DATA>::erase()
{
    SLink<DATA> *n_akt;

    // if list empty or undefined
    if (akt)
    {
	// if current element is the first element
	if (akt == first)
	{
	    // if also the last element, mean one element list
	    if (akt == last)
	    {
		akt_index = -1;
		first = last = NULL;
		n_akt = NULL;
	    }
	    else
	    {
		// current element is the first but not the only one
		(akt->next)->prev = NULL;
		first = akt->next;
		n_akt = first;
		akt_index = 0;
	    }
	}
	else
	{
	    // if is the last element
	    if (akt == last)
	    {
		(akt->prev)->next = NULL;
		last = akt->prev;
		n_akt = NULL;
		akt_index = -1;
	    }
	    else
	    // Element is in the middle of the list
	    {
		(akt->next)->prev = akt->prev;
		(akt->prev)->next = akt->next;
		n_akt = akt->next;
		akt_index++;
	    }
	}

	// delete the object
	delete akt;

	// update current element pointer
	akt = n_akt;

	// update size
	anz--;
	return true;
    }
    return false;
}

template <class DATA>
DATA* LinList<DATA>::get(int i)
// return the i-th element of the list
{
    bool ahead;   // go next if it's true, previous if false
    int j;

    // if i is out of the list
    if (i >= anz)
	return NULL;

    // if i is the current element
    if (i == akt_index)
	return akt->d;

    // if not positionned yet
    if (akt_index == -1)
    {
	// test to know if begin from begining or from the end
	if (i < (anz / 2))
	{
	    akt = first;
	    akt_index = 0;
	    ahead = true;
	}
	else
	{
	    akt = last;
	    akt_index = anz - 1;
	    ahead = false;

	}
    }
    else
    {
	// test with current position 
	if (i < akt_index)
	{
	    // i closest from begin or current position
	    if ((akt_index - i) > i)
	    {
		akt = first;
		akt_index = 0;
		ahead = true;
	    }
	    else
		ahead = false;
	}
	else
	{
	    // i closest from end or current position
	    if ((i - akt_index) > ((anz-1) - i))
	    {
		akt = last;
		akt_index = anz - 1;
		ahead = false;
	    }
	    else
		ahead = true;
	}
    }


    // set position for i 
    if (ahead)
    {
	for (j = akt_index; j < i; j++)
	{
	    if (!akt)
		cout << "LinList::get: List seems to be inkonsistent"  << endl;
	    akt = akt->next;
	}
    }
    else
    {
	for (j = akt_index; j > i; j--)
	{
	    if (!akt)
		cout << "LinList::get: List seems to be inkonsistent"  << endl;
	    akt = akt->prev;
	}
    }

    akt_index = i;
    return akt->d;
}

template <class DATA>
DATA* LinList<DATA>::get_first()
{
    akt = first;

    if (akt != NULL)
    {
	//cout << "akt != null" << endl;
	akt_index = 0;
	return akt->d;
    }
    else
	return NULL;
}

template <class DATA> 
DATA* LinList<DATA>::get_last()
{
    //akt = last;

    if (last != NULL)
    {
	//akt_index = anz - 1;
	return last->d;
    }
    else
	return NULL;
}

template <class DATA> 
DATA* LinList<DATA>::get_next()
{
	if (akt==NULL) return NULL;
    akt = akt->next;
    if (akt != NULL)
    {
	akt_index++;
	return akt->d;
    }
    else
    {
		//cout << "next == NULL" << endl;
	akt_index = -1;
	return NULL;
    }
}

template <class DATA>
DATA* LinList<DATA>::get_prev()
{
	if (akt==NULL) return NULL;
    akt = akt->prev;
    if (akt != NULL)
    {
	akt_index--;
	return akt->d;
    }
    else
    {
	akt_index = -1;
	return NULL;
    }
}

template <class DATA> 
void LinList<DATA>::check()
{
    SLink<DATA> *f, *old_f;
    int myanz;
    char buffer[255];

    old_f = first;
    // if first = null but not empty list : error
    if (old_f == NULL)
    {
		if (last != NULL)
			//error("LinList::check: first == NULL, last != NULL", false);
			cout << "LinList::check: first == NULL, last != NULL" << endl;
		if (anz != 0)
			cout << "LinList::check: first == NULL, anz != 0" << endl;
	return;
    }

    myanz = 1;
    if (old_f->prev != NULL)
    {
	 cout << "LinList::check: Listenkopf.prev ungleich NULL"  << endl;
	return;
    }

    for (f = old_f->next; f != NULL; f = f->next)
    {
	if (f->prev != old_f)
	{
	    cout << "LinList::check: Rueckwaertsverkettung fehlerhaft"  << endl;
            return;
        }
	if (old_f->next != f)
	{
	    cout << "LinList::check: Vorwaertsverkettung fehlerhaft"  << endl;
            return;
        }
	old_f = f;

	myanz ++;
	if (myanz > anz)
	{
	    sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);
	    cout << buffer  << endl;
	    return;
	}
    }

    if (old_f->next != NULL)
    {
	 cout << "LinList::check: Listenende.next ungleich NULL"  << endl;
	return;
    }

    if (last != old_f)
    {
	cout << "LinList::check: last ungleich Listenende"  << endl;
	return;
    }

    if (myanz != anz)
    {
	sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);
	cout << buffer << endl;
    }
}


//resize (only for the linMatrix : DATA = double)
template <class DATA> 
void LinList<DATA>::resize(int i, DATA defaultValue){
	
	for(int j=0; j<i; j++){
		DATA *newDefaultValue  = new DATA(defaultValue);
		insert(newDefaultValue);
	}
}
	 
//set (only for the linMatrix : DATA = double
template <class DATA> 
bool LinList<DATA>::set(int i, DATA *d){
	bool ahead;   // go next if it's true, previous if false
    int j;

    // if i is out of the list
    if (i >= anz)
	return false;

    // if i is the current element
	if (i == akt_index){
		akt->d = d;
		return true;
	}
	

    // if not positionned yet
    if (akt_index == -1)
    {
	// test to know if begin from begining or from the end
	if (i < (anz / 2))
	{
	    akt = first;
	    akt_index = 0;
	    ahead = true;
	}
	else
	{
	    akt = last;
	    akt_index = anz - 1;
	    ahead = false;

	}
    }
    else
    {
	// test with current position 
	if (i < akt_index)
	{
	    // i closest from begin or current position
	    if ((akt_index - i) > i)
	    {
		akt = first;
		akt_index = 0;
		ahead = true;
	    }
	    else
		ahead = false;
	}
	else
	{
	    // i closest from end or current position
	    if ((i - akt_index) > ((anz-1) - i))
	    {
		akt = last;
		akt_index = anz - 1;
		ahead = false;
	    }
	    else
		ahead = true;
	}
    }


    // set position for i 
    if (ahead)
    {
	for (j = akt_index; j < i; j++)
	{
	    if (!akt)
		cout << "LinList::get: List seems to be inkonsistent" << endl;
	    akt = akt->next;
	}
    }
    else
    {
	for (j = akt_index; j > i; j--)
	{
	    if (!akt)
		cout << "LinList::get: List seems to be inkonsistent" << endl;
	    akt = akt->prev;
	}
    }

    akt_index = i;
    akt->d = d;
	return true;
}



////////////////////////////////////////////////////////////////////////
// SortedLinList
////////////////////////////////////////////////////////////////////////
/*
template <class DATA>
class SortedLinList : public LinList<DATA>
{
    bool increasing;
public:
    SortedLinList(bool _doDelete=true);

    virtual void set_sorting(bool _increasing); // wenn increasing gleich true (default), wird
                   						            // aufsteigend einsortiert
    virtual void insert(DATA *f);    			   // fuegt ein Element durch direktes Einfuegen ein
    virtual void sort(bool _increasing);			// sortiert die Liste
    virtual void check();               			// ueberprueft die Konsistenz der Liste
};

template <class DATA>
SortedLinList<DATA>::SortedLinList(bool _doDelete)
    : LinList<DATA>(_doDelete)
{
    increasing = true;
}


template <class DATA>
void SortedLinList<DATA>::set_sorting(bool _increasing)
{
    increasing = _increasing;
}

template <class DATA>
void SortedLinList<DATA>::check()
{
    SLink<DATA> *sd;
    DATA *old;
    bool valid;          // falls true, ist old mit einem Wert besetzt

    // Verkettung konsistent ?
    LinList<DATA>::check();

    // Sortierung korrekt ?
    valid = false;
    for (sd = first; sd != NULL; sd = sd->next)
    {
	 if (valid && (sd->d->distanz) < old->distanz)
         {
	     error("LinList::check: Liste unsortiert", false);
	     return;
         }
	 valid = true;
	 old = sd->d;
    }
}

template <class DATA> 
void SortedLinList<DATA>::insert(DATA *f)
{
    SLink<DATA> *sd;

    // Rahmen fuer neues Datenelement erzeugen
    sd = new SLink<DATA>(doDelete);
    sd->d = f;

    // Liste leer?
    if (first == NULL)
    {
	first = sd;
	last = sd;
	anz = 1;
	sd->next = sd->prev = NULL;

	return;
    }

    // Einfuegestelle bestimmen
    if (increasing)
	for (akt = first; akt != NULL && (akt->d->distanz < f->distanz); akt = akt->next) ;
    else
	for (akt = first; akt != NULL && (akt->d->distanz > f->distanz); akt = akt->next) ;

    // neues Element muss vor akt eingefuegt werden --> Zeiger umbiegen
    if (akt != NULL)
    {
	if (akt == first)
	    first = sd;
	else
	    (akt->prev)->next = sd;
	sd->next = akt;
	sd->prev = akt->prev;
	akt->prev = sd;
    }
    else
    // neues Element muss als letztes Element eingefuegt werden -->
    // Zeiger umbiegen
    {
	sd->prev = last;
	sd->next = NULL;
	last->next = sd;
	last = sd;
    }

    // Gesamtanzahl erhoehen
    anz ++;
    akt_index = -1;
}

template <class DATA>
void SortedLinList<DATA>::sort(bool _increasing)
// Bubblesort der ganzen Liste
{
    SLink<DATA> *old_akt;
    DATA *s;
    bool any, swap;

    set_sorting(_increasing);

    any = true;
    while (any)
    {
	any = false;
	old_akt = NULL;
	for (akt = first; akt != NULL; akt = akt->next)
	{
	    // beim ersten Element gibts nichts zu vergleichen
	    if (old_akt != NULL)
	    {
		swap = false;
		if (_increasing)
		{
		    if ((akt->d->distanz) > (old_akt->d->distanz))
			swap = true;
		}
		else
		{
		    if ((akt->d->distanz) < (old_akt->d->distanz))
			swap = true;
		}

		if (swap)
		{
		    // es muessen nur die Datenpointer umgehaengt werden !
		    s = akt->d;
		    akt->d = old_akt->d;
		    old_akt->d = s;

		    // in diesem Durchlauf hat sich was getan --> 
		    // neuer Durchlauf
		    any = true;
		}
	    }
	    old_akt = akt;
	}    
    }

    akt_index = -1;
}

////////////////////////////////////////////////////////////////////////
// PersistentList
////////////////////////////////////////////////////////////////////////
// fuegt zur Klasse LinList noch Funktionen hinzu, die es erlauben,
// die Hauptspeicherliste auf Platte zu speichern und wieder zu lesen.
// Hierzu muss das Listenelement die Funktionen:
// 
// read_from_buffer 
// write_to_buffer 
// write_data_header
// 
// zur Verfuegung stellen. Diese Funktionen braucht die Liste, da sie
// ja keinerlei Informationen ueber die innere Struktur der Datenelemente
// hat. Ein einfaches Speichern des gesamten Speicherbereichs des Elements
// auf Platte ist wegen des VTable-Pointers nicht moeglich und wegen der 
// Moeglichkeit, dass im Objekt Verweise auf andere Objekte gespeichert 
// sind, die bei einem erneuten Programmlauf und dem Laden der Liste
// keinen Sinn mehr machen wuerden. Um das Element beim Laden richtig 
// erzeugen zu koennen, steht vor jedem Element im File ein Header, 
// dessen Laenge ueber die virtuelle Funktion "get_data_header_size" 
// gesetzt werden kann. Ebenso steht am Anfang des Files ein 
// Header, der beliebig beschrieben werden kann. Um diese Features
// nutzen zu koennen, muss eine von PersistentList abgeleitete Klasse
// die folgenden Funktionen zur Verfuegung stellen:
// 
// get_header_size 
// get_data_header_size
// read_header
// write_header
// 
// Beim Lesen und Schreiben der Liste von Platte ruft PersistentList 
// die Funktion read/write_header mit einem Zeiger auf einen Puffer 
// auf. Die abgeleitete Klasse muss dann aus diesem Puffer ihre Daten 
// lesen bzw. schreiben. 
// Alle Objekte, die in diesem Container gespeichert werden, muessen
// einen Konstruktor KONSTRUKTOR(void *) zur Verfuegung stellen.
// Diesem werden die Headerdaten des einzelnen Elements uebergeben.
// Das File hat damit folgendes Format:
//
//  Byte           Bezeichnung             Inhalt
//  sizeof(int)    Headergroesse             h
//  sizeof(int)    Anzahl d. Elemente        n   
//  sizeof(int)    Datenheadergroesse       dh    
//  h              Header
//
//  n-mal 
//        sizeof(int)    Datengroesse             d
//        dh             Datenheader    
//        d              Daten
////////////////////////////////////////////////////////////////////////

template <class DATA>
class PersistentList : public LinList<DATA>
{
protected:
    virtual int get_header_size()            // liefert Groesse des Headers
    { return 0;}
    virtual int get_data_header_size()       // liefert Groesse des Elementheaders
    { return 0;}
    virtual void read_header(void *buffer)   // liest Header in Objekt ein
    { }
    virtual void write_header(void *buffer)  // liest Header in Objekt ein
    { }
public:
    void save(char *name);      // speichert ganze Liste auf Platte
    void load(char *name);      // liest ganze Liste von Platte
};
*/
/*
template <class DATA> 
int PersistentList<DATA>::get_header_size()
{
    return 0;
}*/



/*
template <class DATA> 
int PersistentList<DATA>::get_data_header_size()
{
    return 0;
}*/
/*
template <class DATA> 
void PersistentList<DATA>::read_header(void *buffer)
{
}

template <class DATA> 
void PersistentList<DATA>::write_header(void *buffer)
{
}
*/
/*
template <class DATA> 
void PersistentList<DATA>::load(char *name)
{
    FILE *fp;
    DATA *d;
    void *buffer, *d_buffer, *header, *d_header;
    int header_size, num_elem, d_header_size, d_size;
    int i;

    // File oeffnen
    fp = fopen(name, "rb");
    if (!fp)
	return;

    // Headergroesse lesen
    if (fread(&header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read size of header from file", true);

    // Elementzahl lesen
    if (fread(&num_elem, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read number of elements from file", 
	      true);

    // Datenheadergroesse lesen
    if (fread(&d_header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read size of data header from file", 
	      true);

    // Header allokieren und einlesen
    header = new char[header_size];
    if (header_size > 0 && fread(header, header_size, 1, fp) != 1)
	error("PersistentList::save: cannot read  header from  file", 
              true);
    read_header(header);

    // Datenheader allokieren
    d_header = new char[d_header_size];

    for (i = 0; i < num_elem; i++)
    {
	// Laenge des Elements einlesen
	if (fread(&d_size, sizeof(int), 1, fp) != 1)
	    error("PersistentList::load: cannot read element size from file", 
		  true);

	// Datenheader einlesen
	if (d_header_size > 0 && fread(d_header, d_header_size, 1, fp) != 1)
	    error("PersistentList::load: cannot read data header from file", 
		  true);

	// neues Element erzeugen
	d = new DATA(d_header);

	// Daten einlesen
	buffer = new char[d_size];
	if (d_size > 0 && fread(buffer, d_size, 1, fp) != 1)
	    error("PersistentList::load: cannot read data from file", 
		  true);
	d->read_from_buffer(buffer);
	delete [] buffer;

	// Element in die Liste einfuegen
	insert(d);
    }

    // Puffer freigeben
    delete [] header;
    delete [] d_header;

    // File schliessen
    fclose(fp);
}

template <class DATA> 
void PersistentList<DATA>::save(char *name)
{
    FILE *fp;
    DATA *d;
    void *buffer, *d_buffer, *header, *d_header;
    int header_size, num_elem, d_header_size, d_size;
    int i;

    // File oeffnen
    fp = fopen(name, "wb");
    if (!fp)
	error("PersistentList::save: cannot open file for writing", true);

    // Headergroesse schreiben
    header_size = get_header_size();
    if (fwrite(&header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write size of header to file", true);

    // Elementzahl schreiben
    num_elem = get_num();
    if (fwrite(&num_elem, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write number of elements to file", 
              true);

    // Datenheadergroesse schreiben
    d_header_size = get_data_header_size();
    if (fwrite(&d_header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write size of data header to  file", 
              true);

    // Header allokieren schreiben
    header = new char[header_size];
    write_header(header);
    if (header_size > 0 && fwrite(header, header_size, 1, fp) != 1)
	error("PersistentList::save: cannot write header to  file", 
              true);

    // Datenheader allokieren
    d_header = new char[d_header_size];

    for (d = get_first(); d != NULL; d = get_next())
    {
	// Laenge des Elements schreiben
	d_size = d->get_size();
	if (fwrite(&d_size, sizeof(int), 1, fp) != 1)
	    error("PersistentList::save: cannot write element size to file", 
                  true);

	// Datenheader schreiben
	d->write_data_header(d_header);
	if (d_header_size > 0 && fwrite(d_header, d_header_size, 1, fp) != 1)
	    error("PersistentList::save: cannot write data header to file", 
		  true);

	// Daten schreiben
	buffer = new char[d_size];
	d->write_to_buffer(buffer);
	if (d_size > 0 && fwrite(buffer, d_size, 1, fp) != 1)
	    error("PersistentList::save: cannot read data from file", 
		  true);
	delete [] buffer;
    }

    // Puffer freigeben
    delete [] header;
    delete [] d_header;

    // File schliessen
    fclose(fp);
}
*/

#endif  // __LINLIST



















